package com.ting.test.algorithms.递归和动态规划.从左往右的模型;

/**
 * 给定3个参数，N，M，K
 * 怪兽有N滴血，等着英雄来砍自己
 * 英雄每一次打击，都会让怪兽流失[0~M]的血量
 * 到底流失多少？每一次在[0~M]上等概率的获得一个值
 * 求K次打击之后，英雄把怪兽砍死的概率
 */
public class 怪兽掉血问题 {

    public static void main(String[] args) {

    }


    /**
     * 该方法返回的是当怪兽还有currentBlood滴血的情况下，再经过restShoot次打击之后，被砍死的次数
     *
     * @param M            每次掉血的最大值 范围在[0,M]
     * @param currentBlood 当前剩余的血量
     * @param restShoot    剩余的攻击次数
     * @return
     */
    public static long process(int M, int currentBlood, int restShoot) {
        if (currentBlood <= 0) {
            //如果没血了 表示当前算一次,即使当前攻击次数还么用完，也没关系，默认后面的次数就是在鞭尸
            //这里需要注意的是 如果当前怪兽已经没血了，但是攻击次数还有，那么针对每一次攻击，都有M+1种掉血的方式
            //并且M+1种方式都是有效的，因为怪兽已经死了，
            //所以返回的有效次数应该是(M+1)^restshoot次
            return (long) Math.pow(M + 1, restShoot);
        }

        //如果攻击次数已经没有了，且血也掉完了，说明怪兽被打死了 否则认为这种方案干不死怪兽
        if (restShoot == 0) {
            return currentBlood == 0 ? 1 : 0;
        }

        int times = 0;
        //从0,M 遍历本次攻击掉血的所有M+1中情况下，怪兽被干死的可能性有几种 获取总和
        for (int i = 0; i <= M; i++) {
            times += process(M, currentBlood - i, restShoot - 1);
        }
        return times;

    }

    /**
     * 该方法返回的是当怪兽还有currentBlood滴血的情况下，再经过restShoot次打击之后，被砍死的次数
     *
     * @param M            每次掉血的最大值 范围在[0,M]
     * @param currentBlood 当前剩余的血量
     * @param restShoot    剩余的攻击次数
     * @return
     */
    public static long dp(int M, int currentBlood, int restShoot) {
        long[][] dp = new long[restShoot + 1][currentBlood + 1];
        dp[0][0] = 1;//根据base case  如果攻击次数已经没有了，且血也掉完了，说明怪兽被打死了 否则认为这种方案干不死怪兽
        //这一步实际上是计算出来了 dp数组的第0行的所有值
        for (int i = 0; i < restShoot; i++) {
            dp[0][i] = (long) Math.pow(M + 1, restShoot);//
        }

        //一定要举例画图 才能发现规律!!!
        int times = 0;
        for (int i = 0; i <= restShoot; i++) {
            for (int j = 1; j <= currentBlood; j++) {
                //从0,M 遍历本次攻击掉血的所有M+1中情况下，怪兽被干死的可能性有几种 获取总和
                for (int m = 0; m <= M; i++) {
                    if (currentBlood - m <= 0) {
                        times += (int) Math.pow(M + 1, restShoot);
                    } else {
                        times += dp[currentBlood - m][restShoot - 1];
                    }
                }
                dp[i][j] = times;
            }
        }
        return dp[restShoot][currentBlood];

    }

    /**
     * 该方法返回的是当怪兽还有currentBlood滴血的情况下，再经过restShoot次打击之后，被砍死的次数
     *
     * @param M            每次掉血的最大值 范围在[0,M]
     * @param currentBlood 当前剩余的血量
     * @param restShoot    剩余的攻击次数
     * @return
     */
    public static long dp2(int M, int currentBlood, int restShoot) {
        long[][] dp = new long[restShoot + 1][currentBlood + 1];
        dp[0][0] = 1;//根据base case  如果攻击次数已经没有了，且血也掉完了，说明怪兽被打死了 否则认为这种方案干不死怪兽
        //这一步实际上是计算出来了 dp数组的第0行的所有值
        for (int i = 0; i < restShoot; i++) {
            dp[0][i] = (long) Math.pow(M + 1, restShoot);//
        }

        for (int i = 0; i <= restShoot; i++) {
            for (int j = 1; j <= currentBlood; j++) {
                //从0,M 遍历本次攻击掉血的所有M+1中情况下，怪兽被干死的可能性有几种 获取总和
                // 根据规律可知 dp[i][j]=dp[i-1][j]+dp[i-1][j-1]-dp[i-1][j-M-1]
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] - dp[i - 1][j - M - 1];
                if (j - M - 1 >= 0) {
                    dp[i][j] = dp[i][j] - dp[i - 1][j - M - 1];
                } else {
                    dp[i][j] = (long) (dp[i][j] - Math.pow(M + 1, i-1));
                }
            }
        }
        return dp[restShoot][currentBlood];

    }

}
